iT邦幫忙

2021 iThome 鐵人賽

DAY 30
1
Software Development

30天用JavaScript刷題刷起來!系列 第 30

Day 30 :BST中找最接近的值&感謝文

  • 分享至 

  • xImage
  •  

簡單敘述一下題目:題目會給你一棵BST以及一個數。我們要從這個BST中找出最接近這個數的節點值。

以下圖為例
https://ithelp.ithome.com.tw/upload/images/20211015/20141729NjBrEMwvYA.png
假設題目要我們找出這棵樹中和12最接近的值,用看的可以知道答案為13。

直覺的想法就是我從根開始,把每個值去和target比較(取相差的絕對值),額外用一個變數(closest)去存現在和target最接近的值找出最接近的。

那麼一開始我們應該要把closest設成無限大,我們從root(10)開始,比較
|infinity - 12(target)|= infinity
|10 - 12| = 2

因為 infinity 遠大於2 , 所以我們可以把 closest從infinity換成10。

我們理所當然可以使用拜訪每個數的節點一個個的確認,但既然題目給我們的樹是BST,我們當然不能忽略這個特性!我們知道現在10左手邊的所有數都一定會比10還要小,而目前要找最靠近12的值,且12又來的比10還大,所以我們根本不需要去查10左手邊以下的數對吧?

所以我們移到了15
|10 - 12|= 2
|15 - 12 |= 3

所以10目前勝利,closet不變。

那思考一下:我們先在該往15的左邊還是右邊找?
想一想!!/images/emoticon/emoticon21.gif
是左邊對吧?因為15現在輸了,我們要找更小的才能更接近12!
接著我們就會發現13,最後會結束在因為13沒有左兒子於是13就是整解。

那我們在想一個問題,我們什麼時候不用繼續找下去?
因為是要找最接近的數,所以當我們遇到絕對值算出來恰為0的時候,應該就可以停止了吧?

平均來看:時間複雜度會是O(logN),N是數的節點數

但最糟的的時候還是有可能來到O(N),當BST只有一個斜斜的樹枝(branch),完全沒佔到BST的優勢。

而空間複雜度會根據我們的程式碼有所不同,如果以遞迴方式(call stack),最糟會來到O(N)。如果用迭代的方式,則空間複雜度會是O(1)。

最後就是程式碼拉!遞迴&迭代兩種都寫寫看~

function findClosestValueInBst(tree, target) {
  return findCloset(tree, target, tree.value);
}

function findCloset(tree, target, closest) {
  if (tree === null) return closest;
  if (Math.abs(target - closest) > Math.abs(target - tree.value)) {
    closest = tree.value;
  }
// recursive
  if (target < tree.value) {
    return findCloset(tree.left, target, closest);
  } else if (target > tree.value) {
    return findCloset(tree.right, target, closest);
  } else {
    return closest;
  }
}

class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function findClosestValueInBst(tree, target) {
  return findCloset(tree, target, tree.value);
}
// iterate
function findCloset(tree, target, closest) {
  let current = tree;
  while (current !== null) {
    if (Math.abs(target - closest) > Math.abs(target - current.value)) {
      closest = current.value;
    }
    if (target < current.value) {
      current = current.left;
    } else if (target > current.value) {
      current = current.right;
    } else {
      break;
    }
  }
  return closest;
}

class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}


終於撐完最後一天了!
必須得說如果不是兩位好隊友,ycchiuuuu & pjchender 的互相鼓勵,我大概第10多天就想偷懶棄賽了/images/emoticon/emoticon70.gif,他們對我來說都是很好的學習榜樣,經驗也比我豐富超多,很推薦大家閱讀React 前端工程師的兩把刷子Javascript 從寫對到寫好

此外,
感謝每一位訂閱我以及曾經閱讀且熱心修正過我文章或是分享心得的讀者,謝謝你們!
/images/emoticon/emoticon41.gif
鐵人賽下台一鞠躬。

結束,是另一個開始。


上一篇
Day 29 : 堆積排序 Heap Sort
系列文
30天用JavaScript刷題刷起來!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
1
pjchender
iT邦新手 3 級 ‧ 2021-10-15 23:12:25

人還在嗎!?

Jen iT邦新手 5 級 ‧ 2021-10-16 00:40:51 檢舉

這要看在哪裡/images/emoticon/emoticon37.gif

1
Wei
iT邦新手 5 級 ‧ 2021-10-17 20:45:16

恭喜完賽~

另外想問 iterate 方法的 else if (target > tree.value) 是否該改成 else if (target > current.value) ?

Jen iT邦新手 5 級 ‧ 2021-10-18 19:56:07 檢舉

謝謝您
可以的 ! 改成current.value 其實更好!已經修正

1
ycchiuuuu
iT邦新手 4 級 ‧ 2021-10-18 16:51:32

恭喜完賽!太用心啦~值得一推的手寫解題文!

最後一天仍然刷好刷滿,沒有像我跑去打心得文XD

Jen iT邦新手 5 級 ‧ 2021-10-18 19:56:54 檢舉

你的心得文還是很有用的 /images/emoticon/emoticon34.gif

我要留言

立即登入留言